perm filename LEIBNI[F84,JMC]1 blob
sn#782644 filedate 1985-01-10 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00003 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 leibni[f84,jmc] Non-monotonic for Association for Symbolic Logic
C00007 00003 abstract
C00010 ENDMK
C⊗;
leibni[f84,jmc] Non-monotonic for Association for Symbolic Logic
Formalized non-monotonic reasoning is an idea that has arisen in
artificial intelligence (AI) and presents interesting mathematical
problems that are important for its AI applications. My goal is to
describe one form of it, {\it circumscription}, to explain its motivation
in terms of formalizing common sense knowledge and reasoning, and to
mention some of the mathematical problems it presents and quote a few of
the results so far obtained.
Leibniz proposed to replace argument by computation. What he
had in mind was to use mathematical logic, which didn't actually
exist in his day, to express agreed on premisses and to verify proposed
conclusions by computation. His attempts to achieve this goal
were very unsuccessful. While he invented binary numbers, perhaps
not for the first time, he didn't even invent propositional calculus.
This is curious, because propositional calculus is
mathematically much simpler than infinitesimal calculus of which he
is the co-inventor. Perhaps part of Leibniz's difficulty came form
the problem he gave himself --- reconciling the doctrines of the
Catholics and the Lutherans.
Boole, who did invent propositional calculus 150 years later,
had similar goals, and entitled his book {\it The Laws of Thought}.
He didn't invent predicate calculus, which had to wait for Frege.
Since Frege's time, mathematical logic has developed enormously,
but attempts to apply it to Leibniz's problem of formalizing
every day argument have been sporadic and mainly unsuccessful.
The logical tools for such an attempt have existed since
Frege's time and took a stable form by the 1920s. One might have
hoped for an attempt to express common sense knowledge in logic
by the 1920s, but it didn't happen. All this suggests that the
difficulties are conceptual rather than technical, and indeed
some people have claimed that mathematical logic has nothing to do with
thought which is inherently non-logical. Such a conclusion is understandable,
since attempts for formalize thought seem to result in confusion,
but I'm convinced it's mistaken. We need some new ideas, but
mathematical logic will play a big role along with them.
Artificial intelligence sets itself the goal of making
computer programs behave intelligently, and this involves another
try at Leibniz's problem. It has often happened that applied
problems have set off new trains of thought in mathematics
even though in principle these lines of work could have
developed from purely mathematical motivations. I'll not
take the time for examples.
Formalizing non-monotonic reasoning seems to be such an
idea. How far it will lead is still unknown.
***
Programs with common sense
abstract
***
My hope is that mathematical logicians will find formalized non-monotonic
reasoning interesting.
It has interesting technical logical problems.
However, I have a somewhat long shot hope that logicians will
be interested in the conceptual problems of formalizing common sense.
****
hope slide
bibliographic slide
Leibniz's idea and its slow realization
AI attempts to realize Leibniz's idea
We pass lightly over the wandering in the wilderness
of trying to do it all in unmodified logic. Perhaps there
can be a slide illustrating frame axioms.
Non-monotonic reasoning.
slide on non-monotonicity
McDermott-Doyle slide
Reiter slide
orderings
the n uses of non-monotonic reasoning
36 views of Mt. Fuji
The dog problem
The problem is difficult for humans, but the solution
is easy to accept. The reasoning is not deep for us.
Formalization of the reasoning starting from only what
can be presumed to be in a common sense data base is a
presently unsolved problem.
examples of c.
isblock a ∧ isblock b
isblock a ∨ isblock b
natural numbers
relation of c. to induction (admit some ignorance)
more general in one respect because it isn't afraid of disjunction
interest includes finite cases
m and c.
abnormality
birds
painting and moving
Mathematical problems of circumscription.
1. When does minimal model exist?
2. When does c collapse to a first order formula?
3. When is c decidable?
4. When is a problem solver possible.
While formalizing non-monotonic reasoning helps,
more conceptual advances are required before common sene
knowledge and reasoning can be fully formalized.